package com.example.leetcode.c901_end.c1122;
/**
 * 给你两个数组，arr1 和 arr2，
 *
 * arr2 中的元素各不相同
 * arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 *
 *  
 *
 * 示例：
 *
 * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 * 输出：[2,2,2,1,4,3,3,9,6,7,19]
 *  
 *
 * 提示：
 *
 * arr1.length, arr2.length <= 1000
 * 0 <= arr1[i], arr2[i] <= 1000
 * arr2 中的元素 arr2[i] 各不相同
 * arr2 中的每个元素 arr2[i] 都出现在 arr1 中
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/relative-sort-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.*;
import java.util.stream.Collectors;

/**
 * 数组的相对排序
 * @author zhanpengguo
 * @date 2020-11-14 10:08
 */
public class Solution {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> counts = new HashMap<>();
        int[] ans = new int[arr1.length];
        for (int a : arr1) {
            counts.put(a, counts.getOrDefault(a, 0) + 1);
        }
        int index = 0;
        for (int a : arr2) {
            for (int i = 0; i < counts.get(a); i++) {
                ans[index++] = a;
            }
            counts.put(a, 0);
        }
        List<Map.Entry<Integer, Integer>> collect = counts.entrySet().stream()
                .filter(e -> e.getValue() != 0)
                .sorted(Comparator.comparingInt(Map.Entry::getKey))
                .collect(Collectors.toList());
        for (Map.Entry<Integer, Integer> entry : collect) {
            int count = entry.getValue();
            for (int i = 0; i < count; i++) {
                ans[index++] = entry.getKey();
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr1 = {2};
        int[] arr2 = {};
        Solution solution = new Solution();
        int[] ints = solution.relativeSortArray(arr1, arr2);
        System.out.println(Arrays.toString(ints));
    }
}
